/**
 * 1095. 山脉数组中查找目标值
 * https://leetcode-cn.com/problems/find-in-mountain-array/
 */
public class Solutions_1095 {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 3, 1};
        int target = 3;  // output: 2

//        int[] array = {0, 1, 2, 4, 2, 1};
//        int target = 3;  // output: -1

//        int[] array = {1, 5, 2};
//        int target = 0;  // output: -1

        MountainArray obj = new MountainArray(array);
        int result = findInMountainArray(target, obj);
        System.out.println(result);
    }

    /**
     * 解题思路：
     * 既然是山脉数组，那么就一定有个顶峰
     * 通过二分查找找到顶峰所在的位置
     * 若顶峰就是 target，则直接返回结果
     * 否则对顶峰的左边山坡（元素是正序的）和右边山坡（元素是逆序的）分别进行二分查找
     */
    public static int findInMountainArray(int target, MountainArray mountainArr) {
        // 二分法找到峰顶所在的索引
        int peak = findPeak(mountainArr);
        if (mountainArr.get(peak) == target) {
            return peak;
        }
        int leftRes = findInArray1(0, peak - 1, mountainArr, target);
        if (leftRes != -1) {
            // 既然左侧找到目标值了，就不用再去右侧找了，因为下标要尽可能的小
            return leftRes;
        }
        int rightRes = findInArray2(peak + 1, mountainArr.length() - 1, mountainArr, target);
        return rightRes;
    }

    // 逆序数组中二分查找
    // 5 4 3 2 1
    public static int findInArray2(int left, int right, MountainArray mountainArr, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int num = mountainArr.get(mid);
            if (num == target) {
                return mid;
            } else if (num < target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    // 正序数组中二分查找
    // 1 2 3 4 5
    public static int findInArray1(int left, int right, MountainArray mountainArr, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int num = mountainArr.get(mid);
            if (num == target) {
                return mid;
            } else if (num < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static int findPeak(MountainArray obj) {
        int left = 0, right = obj.length() - 1;
        int len = obj.length();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid + 1 < len && obj.get(mid) < obj.get(mid + 1)) {
                // 舍弃 [left, mid] 部分
                left = mid + 1;
            } else {
                // 舍弃 [mid + 1, right] 部分
                right = mid;
            }
        }
        return left;
    }
}

class MountainArray {
    int[] nums;
    int len;

    public MountainArray(int[] nums) {
        this.nums = nums;
        len = nums.length;
    }

    public int get(int index) {
        return nums[index];
    }

    public int length() {
        return len;
    }
}
